#include <stdlib.h>
#include <stdio.h>
#include "Arbre.h"

void initialiserArbre(Arbre * A)
{
    A->adRacine = NULL;
    A->nbElemDansArbre = 0;
}

int testArbreVide(const Arbre * A)
{
    if(A->adRacine == NULL) return 1;
    return 0;
}

int testNoeudVide(const Noeud * pN)
{
    if(pN == NULL) return 1;
    return 0;
}

static void insererElementDansSSArbre(ElementA e, Noeud * ppN, Arbre *A)
{
 Noeud * tmp;
	tmp = (Noeud*) malloc(sizeof(Noeud));
	if (estSuperieurOuEgalElementA(e,ppN->info) == 0 && ppN->fg != NULL)
	{
		insererElementDansSSArbre(e,ppN->fg,A);
	}
	else if (estSuperieurOuEgalElementA(e,ppN->info) == 0 && ppN->fg == NULL)
	{

		tmp->info =e;
		tmp->fd = NULL;
		tmp->fg = NULL;
		ppN->fg = tmp;
	}
	else if (estSuperieurOuEgalElementA(e,ppN->info) == 1 && ppN->fd != NULL)
	{
		insererElementDansSSArbre(e,ppN->fd,A);
	}
	else if (estSuperieurOuEgalElementA(e,ppN->info) == 1 && ppN->fd == NULL)
	{
		tmp->info = e;
		tmp->fd = NULL;
		tmp->fg = NULL;
		ppN->fd = tmp;
}

void insererElementArbre(ElementA e, Arbre * A)
{

  Noeud *tmp;
	if (testArbreVide(A))
	{
		tmp = (Noeud*) malloc(sizeof(Noeud));
		tmp->info = e;
		tmp->fg = NULL;
		tmp->fd = NULL;
		A->adRacine = tmp;
		A->nbElemDansArbre++;
	}
	else
	{
		insererElementDansSSArbre(e,tmp,A);
		A->nbElemDansArbre++;
	}
}



static void detruireAPartirDe(Noeud *pN, Arbre *pA)
{
  if(pN->fg == NULL && pN->fd == NULL)
	{
		free(pA);
		pN = NULL;
	}
	else if (pN->fg == NULL)
	{
		detruireAPartirDe(pN->fd,pA);
	}
	else if (pN->fd == NULL)
	{
		detruireAPartirDe(pN->fg,pA);
	}
	else
	{
		detruireAPartirDe(pN->fd,pA);
		detruireAPartirDe(pN->fg,pA);
	}
}

void testamentArbre(Arbre *A)
{

	detruireAPartirDe(A->adRacine,A);
	A->nbElemDansArbre = 0;
	A->adRacine = NULL;

}



void rechercherElementArbreElement(ElementA e, Arbre A, int * trouve, int * nb_visites)
{
	Noeud * parcour;
	parcour = A.adRacine;
	while(parcour != NULL && *trouve != 1)
	 {
		if(e < parcour->info){
			*nb_visites= *nb_visites + 1;
			parcour = parcour->fg ;
		}
		if(e > parcour->info){
			*nb_visites= *nb_visites + 1;
			parcour = parcour->fd ;
		}
		if(e == parcour->info){
			*trouve=1;
		}
	}
}

static int calculHauteurDepuisSSArbre(const Noeud * pN)
{

  if(testArbreVide(pN) == 0)
	{
		return -1;
	}
	else
	{
		return (1 + (max((calculHauteurDepuisSSArbrehauteurArbre(pN->fg)(calculHauteurDepuisSSArbrehauteurArbre(pN->fd))))));
	}

}


int hauteurArbre(const Arbre * A)
{
	calculHauteurDepuisSSArbre(A->adRacine);
}


static int somme_profondeurs_depuis_Noeud(Noeud *pN, int prof)
{


	if(testNoeudVide(pN) == 0)
	{
		return prof;
	}
	else
	{
		return prof = 1 + (max((somme_profondeurs_depuis_Noeud(pN->fd)(somme_profondeurs_depuis_Noeud(pN->fg)))));
	}

}

double profondeurMoyenneArbre(Arbre *A)
{
	somme_profondeurs_depuis_Noeud(A->adRacine,0)/hauteurArbre(A);
}



